The present invention relates to a technique of controlling the flow of data such as IP packets on the Internet.
Recently, without being restricted to the best-effort-type service, the quality of services (QoS) including transmission delay, variations in delay, minimum guaranteed speed, or peak speed has been importantly concerned even when information on voice, images and so on are transferred in real time under the traffic control on the Internet.
The content of QoS to be required depends on the IP traffic. For example, requirements for transmission delay are not strict in the case of the best-effort-type traffic. In contrast, in the case of image information, strict requirements are required for transfer delay or variations in delay in order to avoid interruption of images.
In order to realize an optimum quality of services (QoS) for each IP (Internet Protocol) traffic, the IETF (Internet Engineering Task Force) is studying to standardize the specificationsxe2x80x94Intserv (integrated services) and Diffserv (differentiated services)xe2x80x94. In the Intserv specification, QoS is guaranteed by reserving an end to end range using RSVP (resource reservation protocol). In the Diffserv specification, in order to realize QoS on, particularly, the backbone network, priority information is added to each IP packet so that the traffic flowing on the backbone is controlled.
Moreover, since QoS can be guaranteed for each connection in the asynchronous transfer mode (ATM), the approach of mapping QoS of an IP packet on the ATM connection is taken as means of providing QoS of an IP packet in the ATM.
In order to guarantee QoS through the mapping, a data flow (hereinafter referred to as xe2x80x9cflowxe2x80x9d) being formed of a sequence of IP packet groups is identified so that QoS is set in accordance with the identified flow.
The flow is identified for each data based on various data combinations. The data combination is formed by selecting all fields or a specific field only of fields within the header of an IP packet according to a difference of the flow type or the presence or absence of a specific transmission source or transmission destination.
In other words, fields including xe2x80x9cTOS (type of services)xe2x80x9d within the header of an IP packet, xe2x80x9cPROTOCOLxe2x80x9d of an IP packet defining a network layer protocol, xe2x80x9csource address (SA)xe2x80x9d being a source address, xe2x80x9cdestination address (DA)xe2x80x9d being a destination address, and xe2x80x9csource port (SPORT)xe2x80x9d or xe2x80x9cdestination port (DPORT)xe2x80x9d of TCP (transmission control protocol) header or UDP (user datagram protocol) header defining a transport layer protocol are handled as flow identification objects.
A selective combination of specific fields of those fields, for example, a combination of xe2x80x9cSAxe2x80x9d and xe2x80x9cDAxe2x80x9d, a combination of xe2x80x9cSPORTxe2x80x9d and xe2x80x9cDPORTxe2x80x9d, or a combination of xe2x80x9cSAxe2x80x9d, xe2x80x9cDAxe2x80x9d, xe2x80x9cSPORTxe2x80x9d, xe2x80x9cDPORTxe2x80x9d and xe2x80x9cPROTOCOLxe2x80x9d, becomes an actual object for flow identification.
As described above, there are a great number of fields to be selected for flow identification. Data of each field is represented in plural bitsxe2x80x9416 bits or 32 bitsxe2x80x94. For that reason, the number of bits for the retrieval key is increased for flow identification. As a result, outputting the flow identification result with the retrieval table largely widens the bit width of the retrieval key for the retrieval table.
The various combinations of fields for actual identification of fields require complicated identification rules for flow identification. Conventionally, in order to deal with such requirements, the flow identification is performed by software.
However, it is difficult to implement high speed flow identification in the software processing. An increasing number of heavy traffics to be handled occur a bottleneck in processing, thus resulting in congestion in a network. For that reason, an application range for the flow identification by software is limited to small size networks such as LANs (local area networks) or to areas with a relatively small number of traffics such as access systems of WANs (wide area networks).
In near future, the traffic of an IP packet is expected to increase explosively. For that reason, it is considered that even small size networks such as LANs or access systems in WANs will require the system that can deal with a large volume of traffics.
The ATM has the advantage of performing traffic control by hardware every logical link, so that the type of services (QoS) can be ensured without occurring a process bottleneck even on high-speed broadband networks. However, the high-speed technique in a hardware level has not been yet established even in the ATM to map the flow of an IP packet to an ATM logical link compatible QoS. For that reason, the intervention of software is needed to the QoS mapping and a high-speed flow identification process has been not realized.
Recently, content-addressable memory (CAM) has been used in the field of address retrieval in the network system devices. The content-addressable memory determines a memory location through label association and indicates it with the content, not address. The content-addressable memory can retrieve data on the retrieval data table at high speed. Since the capacity of a content-addressable memory depends on only the number of entries, the content-addressable memory can retrieve data with large data bit width at high speed, without an increase of the capacity.
However, the content-addressable memory can perform only the exact matching retrieval. In order to configure a retrieval table for flow identification with the content-addressable memory, it is required to register entries in which combinations of all fields to be selectable for flow identification correspond to all flow identification results. In this case, an enormous number of registration entries lead to a expanded retrieval table. The enormous number of registration entries takes much time for retrieval, thus making it difficult to implement a high-speed process for flow identification. For example, where the total number of bits of each field in a header is 128 bits, it is necessary to register entries of 128th power of 2. This is not realistic. Therefore, it has been difficult to configure the flow retrieval table with content-addressable memory.
The present invention is made to overcome the above-mentioned problems. An object of the present invention is to provide a flow identification technique that can implement a flow identification process at high speed.
The present inventor of this application noticed that the field of a header for actual flow identification is usually a part of the entire field. The present inventor has come to the idea that the number of entries of the retrieval table will be able to be decreased by masking a field based on an input logical link number of received data and extracting the field only for actual flow identification. As a result, a content-addressable memory (CAM) can be used, thus speeding the flow identification process.
According to the present invention, the flow identification device comprises a retrieval flag table for storing an input logical link number of received data and a retrieval flag in a corresponding relationship, the retrieval flag setting a field to be retrieved among fields in a header of a received IP (internet protocol) packet terminating the received data, and for outputting a retrieval flag corresponding to an input logical link number extracted from the received data; a mask section for masking each field in a header of the received IP packet with the retrieval flag and creating a post-mask retrieval key; and a flow retrieval table configured of a content-addressable memory, for storing the post-mask retrieval key and a flow identification result in a corresponding relationship and outputting a flow identification result corresponding to a post-mask retrieval key output from the retrieval flag table.
As described above, in the flow identification device of the present invention, a retrieval flag table is provided that sets a retrieval flag indicating a field for flow retrieval among fields of a packet header every input logical link number. Each field of a package header extracted from a received IP packet is masked with the retrieval flag to create a post-mask retrieval key. The use of the post-mask retrieval key allows the number of entries to the flow retrieval table to be reduced. As a result, the content-addressable memory that can execute only the exact matching can be utilized as a flow retrieval table for flow identification, thus performing high-speed flow identification.
The flow identification device of the present invention can ensure the quality of services (QoS) without bottlenecking the process even on the high-speed broadband network. This device is preferably used even in the area requiring high throughputs such as backbone networks.
Moreover, the use of the content-addressable memory as a flow retrieval table allows the flow identification process to be performed at high speed. Moreover, the use of the content-addressable memory can prevent the flow retrieval table from being large scaled.
Since the flow retrieval table is not large scaled, the IP flow, which can be conventionally realized with only the software, a flow identification process for the ATM logical link compatible QoS mapping, can be realized with hardware such as dedicated LSI chips. The use of hardware enables the flow identification process at higher speed.
For example, either information directly indicating the setting of QoS or information indirectly including information for QoS setting may be output as a flow identification result. In such a case, the retrieval key for retrieving information for setting QoS may be output.
According to the present invention, the flow retrieval table stores a corresponding numerical value in a field to be validated in retrieval as the retrieval flag and an invalid value in a field to be invalidated in retrieval.
By registering a value that indicates invalid in the field to be invalidated, the retrieval flag can be easily utilized as a mask.
According to the present invention, the retrieval flag indicates valid or invalid of respective bits forming the field.
As described above, a post-mask retrieval key, in which the field is partially masked, can be created by using the mask of a bitmap to respective bits forming a field. As a result, for example, all destination addresses and all transmission addresses, in which partial bits of the network address are common, can be handled as targets at the same time.
According to the present invention, when the received data is an ATM (asynchronous transfer mode) cell, one or both of a virtual path identifier and a virtual channel identifier are used as the input logical link number and as the output logical link number.
According to the present invention defined in claim 5 of the present invention, when the received data is a frame relay, DLCI (data link connection identifier) is used as the input logical link number and as the output logical link number.
According to the present invention, when received data is for an ATM cell or a frame relay, the post-mask retrieval key can be easily obtained by referring to the retrieval flag table.
According to the present invention, fields for TOS (type of services), PROTOCOL, source address (SA), and destination address (DA) of an IP header as well as fields for a source port (SPORT) and a destination port (DPORT) of TCP (transmission control protocol) or UDP (user datagram protocol) header are included as the header field of the packet.
Since the above-mentioned field is selected as flow identification target, flow identification can be accurately performed.
According to the present invention, the flow processing device comprises a receiving section for extracting an input logical link number from received data and terminating the received data and creating a received IP packet; a packet receiving and processing section for extracting each field of a header as a retrieval key from the received IP packet and extracting a destination address and outputting a packet; a retrieval flag table for storing the input logical link number and a retrieval flag in a correspondence relationship, the retrieval flag setting a field to be retrieved among fields of the header of the received IP packet, and for outputting a retrieval flag corresponding to an input logical link number extracted by the receiving section; a mask section for masking each field of a header of a received IP packet with the retrieval flag and creating a post-mask retrieval key; a flow retrieval table for storing a post-mask key and a flow retrieval as a flow identification result in a correspondence relationship and outputting a flow retrieval corresponding to a post-mask retrieval key output from the retrieval flag table, the flow retrieval table being formed of a content-addressable memory; a forwarding table for storing a destination address of a header of the received IP packet and a forwarding retrieval in a correspondence relationship and outputting a forwarding retrieval corresponding to a destination address output from the packet receiving and processing section; a flow action table for storing a group of the flow retrieval and the forwarding retrieval and flow action information having information setting QoS (quality of services) and an output logical link number in a correspondence relationship and for outputting flow action information and an output logical link number, corresponding to a group of a flow retrieval output from the flow retrieval table and a forwarding retrieval output from the forwarding table; a packet transmission and processing section for processing a packet output from the packet receiving and processing section based on flow action information output from the flow action table and for creating a transmission IP packet; and a transmission section for disassembling the transmission IP packet to create a transmission cell and transmitting the transmission cell to an address indicating an output logical link number output from the flow action table.
In the flow processing device of the present invention, a post-mask retrieval key created by the mask section is used with a retrieval flag retrieved from the retrieval flag table so that the number of entries to the flow retrieval table can be decreased. As a result, since the content-addressable memory, that can perform only the exact matching, can be used for flow identification as a flow retrieval table, the flow identification can be easily processed at high speed.
Moreover, the use of the content-addressable memory as a flow retrieval table enables high-speed flow identification and can avoid an enlarged flow retrieval table.
The IP flow, which can be conventionally realized with only the software, a flow identification process for the ATM logical link compatible QoS mapping, can be realized with hardware such as dedicated LSI chips. The use of hardware allows the flow identification to be executed at higher speed.
According to the present invention, when the receiving section receives received data from any one of plural input ports and the transmission section transmits transmission data to any one of plural output ports, the receiving section outputs an input physical port number to the retrieval flag table, in addition to the input logical link number, the input physical port number indicating an input port which has received the received data, among the input ports and the flow action table outputs an output physical port number to the transmission section, in addition to an output logical link number, the output physical port number indicating an output port outputting the transmission data among the output ports.
Adding the input physical port number to a retrieval key of the retrieval flag table makes it possible to easily identify a flow received from a different port.
According to the present invention, a flow identification method comprising the steps of retrieving a retrieval flag corresponding to an input logical link number extracted from received data from a retrieval flag table, the retrieval flag table storing an input logical link number of received data and a retrieval flag setting a field to be retrieved among fields of a header of a received IP packet terminating the received data; creating a post-mask retrieval key by masking each field of a header of the IP packet with the retrieval flag; and storing a post-mask retrieval key and a flow identification result in a correspondence relationship and outputting a flow identification result corresponding to a post-mask retrieval key output from the retrieval flag table from a flow retrieval table, the flow retrieval table being configured of a content-addressable memory.
According to the present invention, a flow processing method comprising the steps of extracting an input logical link number from received data and terminating the received data and creating a received IP packet; extracting each field of a header as a retrieval key from the received IP packet while extracting a destination address; retrieving a retrieval flag corresponding to an input logical link number extracted from received data from a retrieval flag table, the retrieval flag table storing the input logical link number and a retrieval flag setting a field to be retrieved among fields of a header of the received IP packet in a correspondence relationship; creating a post-mask retrieval key by masking each field of a header of a received IP packet with the retrieval flag; storing a post-mask retrieval key and a flow retrieval as a flow identification result including information for setting QoS (quality of services) in a correspondence relationship and retrieving a flow retrieval corresponding to a post-mask retrieval key output from the retrieval flag table from a flow retrieval table, the retrieval table being configured of a content-addressable memory; retrieving a forwarding index corresponding to a destination address extracted from a received IP packet from a forwarding table, the forwarding table storing a destination address of a header of the received IP packet and a forwarding index in a correspondence relationship; retrieving flow action information and an output logical link number, corresponding to a group of a flow index retrieved with the flow retrieval table and corresponding to a forwarding index output with reference to a flow action table, the flow action table storing a group of the flow index and the forwarding index and flow action information including indication information setting QoS and an output logical link number, in a correspondence relationship; processing the received IP packet based on flow action information output from the flow action table to create a transmission IP packet; and creating transmission data based on the transmission IP packet and transmitting the transmission data to a destination indicating an output logical link number output from the flow action table.
As described above, according to the flow identification method and the flow processing method of the present invention, a post-mask retrieval key created by the mask section is used with a retrieval flag retrieved from the retrieval flag table. Thus, the number of entries to the flow retrieval table can be reduced. As a result, the content-addressable memory, which can perform only the exact matching, can be utilized for flow identification as a flow retrieval table so that the flow identification can be performed at high speed.